home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 6_11.lha / 6_11 / 6_11_mul.c < prev    next >
Text File  |  1993-08-08  |  3KB  |  126 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. *
  6.    Multiply u[1..n] * v[1..m] to form w[0..m+n]
  7.  
  8.    Based on:
  9.  
  10.    The Art of Computer Programming, volume 2
  11.    D. Knuth, Section 4.3.1, Algorithm M
  12. /
  13. include <arbint.h>
  14. include <debug.h>    /* DELETE */
  15.  
  16. rbint operator*(const arbint& tmp_u,
  17.    const arbint& tmp_v)
  18.  
  19.    // Make u (the multiplicand) and
  20.    // v (the multiplier) positive.
  21.    int negu = tmp_u.isneg();
  22.    int negv = tmp_v.isneg();
  23.    arbint u(+tmp_u);
  24.    if (negu) u = -tmp_u;
  25.    arbint v(+tmp_v);
  26.    if (negv) v = -tmp_v;
  27. f (debug&8)    cerr << "operator*\n";    // DELETEdif (debug&8)    outputarb(cerr, "\tu=", u.p->value, u.p->length, u.p->refcnt);    // DELETE
  28. f (debug&8)    outputarb(cerr, "\tv=", v.p->value, v.p->length, v.p->refcnt);    // DELETE
  29.  
  30.    // The product will be negative if
  31.    // the signs of the multiplier and
  32.    // multiplicand do not match.
  33.    int negans = (negu != negv);
  34.  
  35.    int n = u.p->length;
  36.    int m = v.p->length;
  37.    int wlen = n + m + 1;
  38.    ARB_type *wv = new ARB_type[wlen];
  39.    ARB_type *uv = u.p->value;
  40.    ARB_type *vv = v.p->value;
  41.  
  42.    /*
  43. M1(a) [Initialize]
  44.     Set w[m+1..m+n] <- 0
  45.    */
  46.    memset((char*)wv, 0, wlen * sizeof(ARB_type));
  47. f (debug&8)    { outputarb(cerr, "\twv=", wv, wlen);    // DELETE
  48. err << "\tn=" << n << ", m=" << m << ", wlen=" << wlen << "\n"; } // DELETE
  49.  
  50.    /*
  51. M1(b) [Initialize]
  52.     Set j <- m
  53. M6 [Loop on j]
  54.     decrease j by one
  55.     if j > 0, goto M2
  56.    */
  57.    for (int j = m - 1; j >= 0; j-- )
  58. {
  59. /*
  60.     M2 [zero multiplier?]
  61.     if v[j] == 0
  62.         w[j] <- 0
  63.         goto M6
  64. */
  65. f (debug&8)/*DELETE*/    cerr << "\tj=" << j << "\n";
  66. f (debug&8)/*DELETE*/    cerr << "\tvv[" << j << "]=" << form("%4.4x", vv[j]) << "\n";d    if (vv[j] == 0)
  67.     {d
  68. bug&8)/*DELETE*/    cerr << "\tsetting wv[" << j << "] <- 0\n";
  69.     wv[j] = 0;
  70.     continue;
  71.     }
  72.  
  73. /*
  74.     M3 [Initialize i]
  75.     set i <- n,
  76.         k <- 0
  77.     M5(a) [Loop on i]
  78.     decrease i by one
  79.     if i > 0, goto M4
  80. */
  81. ARB_Ltype v_j = vv[j];
  82. ARB_Ltype k = 0;
  83. for (int i = n - 1, iplusj = i + j + 2;
  84.      i >= 0;
  85.      i--, iplusj--)
  86.  
  87.     {
  88. f (debug&8)/*DELETE*/    cerr << "\ti=" << i << "\n";dif (debug&8)/*DELETE*/    cerr << "\tuv[" << i << "]=" << form("%4.4x", uv[i]) << "\n";
  89. f (debug&8)/*DELETE*/    cerr << "\twv[" << iplusj << "]=" << form("%4.4x", wv[iplusj]) << "\n";
  90. f (debug&8)/*DELETE*/    cerr << "\tk=" << k << "\n";d        /*
  91.     M4 [multiply and add]
  92.         set t <- u[i] * v[j] +
  93.              w[i+j] + k
  94.         w[i+j] <- t % b
  95.         k <- t / b
  96.     */
  97.     ARB_Ltype t = uv[i] * v_j +
  98.     wv[iplusj] + k;
  99.     wv[iplusj] = t;        // % ARB_base;
  100.     k = t / ARB_base;
  101.     }
  102.  
  103. bug&8)/*DELETE*/    cerr << "\tend of loop on i\n";
  104. f (debug&8)/*DELETE*/    cerr << "\tk=" << k << "\n";
  105. f (debug&8)/*DELETE*/    cerr << "\twv[" << (j+1) << "]<-" << form("%4.4x", k) << "\n";d    /*
  106.     M5(b) [Loop on i]
  107.     if i <= 0,
  108.         set w[j] <- k
  109. */
  110. wv[j+1] = k;
  111. }
  112.  
  113.    /* Normalize */
  114. f (debug&8)/*DELETE*/    cerr << "\tend of loop on j\n";
  115. f (debug&8)    outputarb(cerr, "\tw=", wv, wlen);    // DELETE
  116.    arbint w(wv, wlen);
  117. f (debug&8)    outputarb(cerr, "\tw=", w.p->value, w.p->length, w.p->refcnt);    // DELETEdif (debug&8)    outputarb(cerr, "\tu=", u.p->value, u.p->length, u.p->refcnt);    // DELETE
  118. f (debug&8)    outputarb(cerr, "\tv=", v.p->value, v.p->length, v.p->refcnt);    // DELETE
  119.  
  120.    /* Restore sign and return */
  121.    if (negans)
  122. return -w;
  123.    elsR
  124. return w;
  125.  
  126.